/*
Date:20220302 15:10 Pm
key:注意一个元素的情况
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* head=NULL;
    //Node* pre=NULL;
    void Put(Node* root,Node*&pre)
    {
        if(root==NULL){return;}
        else
        {
            Put(root->left,pre);
            if(pre==NULL)
            {
                //cout<<root->val;
                head=root;
                pre=root;
            }
            else
            {
                pre->right=root;
                root->left=pre;
                pre=root;
            }
            //v.push_back(root);
            Put(root->right,pre);
        }
    }
    Node* treeToDoublyList(Node* root) {
        if(root==NULL){return NULL;}
        Node* pre=NULL;
        Put(root,pre);
        Node*p=head;
        for(;p->right!=NULL;p=p->right)
        {
            //cout<<p->val;
        }
        head->left=p;
        p->right=head;
        return head;
    }
};